{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cat and Mouse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #memoization #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #记忆化搜索 #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: catMouseGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #猫和老鼠"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>两位玩家分别扮演猫和老鼠，在一张 <strong>无向</strong> 图上进行游戏，两人轮流行动。</p>\n",
    "\n",
    "<p>图的形式是：<code>graph[a]</code> 是一个列表，由满足&nbsp;<code>ab</code> 是图中的一条边的所有节点 <code>b</code> 组成。</p>\n",
    "\n",
    "<p>老鼠从节点 <code>1</code> 开始，第一个出发；猫从节点 <code>2</code> 开始，第二个出发。在节点 <code>0</code> 处有一个洞。</p>\n",
    "\n",
    "<p>在每个玩家的行动中，他们 <strong>必须</strong> 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 <code>1</code> ，那么它必须移动到 <code>graph[1]</code> 中的任一节点。</p>\n",
    "\n",
    "<p>此外，猫无法移动到洞中（节点 <code>0</code>）。</p>\n",
    "\n",
    "<p>然后，游戏在出现以下三种情形之一时结束：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果猫和老鼠出现在同一个节点，猫获胜。</li>\n",
    "\t<li>如果老鼠到达洞中，老鼠获胜。</li>\n",
    "\t<li>如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一张图 <code>graph</code> ，并假设两位玩家都都以最佳状态参与游戏：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果老鼠获胜，则返回&nbsp;<code>1</code>；</li>\n",
    "\t<li>如果猫获胜，则返回 <code>2</code>；</li>\n",
    "\t<li>如果平局，则返回 <code>0</code> 。</li>\n",
    "</ul>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/17/cat1.jpg\" style=\"width: 300px; height: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/17/cat2.jpg\" style=\"width: 200px; height: 200px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,3],[0],[3],[0,2]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= graph.length &lt;= 50</code></li>\n",
    "\t<li><code>1&nbsp;&lt;= graph[i].length &lt; graph.length</code></li>\n",
    "\t<li><code>0 &lt;= graph[i][j] &lt; graph.length</code></li>\n",
    "\t<li><code>graph[i][j] != i</code></li>\n",
    "\t<li><code>graph[i]</code> 互不相同</li>\n",
    "\t<li>猫和老鼠在游戏中总是可以移动</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cat-and-mouse](https://leetcode.cn/problems/cat-and-mouse/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cat-and-mouse](https://leetcode.cn/problems/cat-and-mouse/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]', '[[1,3],[0],[3],[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        if 0 in graph[1]:\n",
    "            return 1\n",
    "        n = len(graph)\n",
    "        cat_m = [[0 for _ in range(n)] for _ in range(n - 1)]\n",
    "        mouse_m = [[0 for _ in range(n)] for _ in range(n - 1)]\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            cat_m[i][0] = 1\n",
    "            mouse_m[i][0] = 1\n",
    "            cat_m[i][i + 1] = 2\n",
    "            mouse_m[i][i + 1] = 2\n",
    "            for j in graph[0]:\n",
    "                if j != i + 1:\n",
    "                    mouse_m[i][j] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in graph[i]:\n",
    "                if j:\n",
    "                    cat_m[i - 1][j] = 2\n",
    "        flag = True\n",
    "        while not mouse_m[1][1] and flag:\n",
    "            flag = False\n",
    "            for i in range(1, n):\n",
    "                for j in range(1, n):\n",
    "                    if mouse_m[i - 1][j] == 0:\n",
    "                        s = 2\n",
    "                        for p in graph[j]:\n",
    "                            if cat_m[i - 1][p] == 1:\n",
    "                                s = 1\n",
    "                                break\n",
    "                            if cat_m[i - 1][p] == 0:\n",
    "                                s = 0\n",
    "                        if s != 0:\n",
    "                            mouse_m[i - 1][j] = s\n",
    "                            flag = True\n",
    "                    if cat_m[i - 1][j] == 0:\n",
    "                        s = 1\n",
    "                        for p in graph[i]:\n",
    "                            if p != 0:\n",
    "                                if mouse_m[p - 1][j] == 2:\n",
    "                                    s = 2\n",
    "                                    break\n",
    "                                if mouse_m[p - 1][j] == 0:\n",
    "                                    s = 0\n",
    "                        if s != 0:\n",
    "                            cat_m[i - 1][j] = s\n",
    "                            flag = True\n",
    "        return mouse_m[1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 定义常量表示游戏结果\n",
    "# DRAW = 0        # 平局\n",
    "# MOUSE_WIN = 1   # 老鼠获胜\n",
    "# CAT_WIN = 2     # 猫获胜\n",
    "\n",
    "# class Solution:\n",
    "#     def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "#         n = len(graph)\n",
    "        \n",
    "#         # 初始化动态规划数组，用于记忆游戏结果\n",
    "#         # dp[mouse][cat][turns] 表示在老鼠位置为 mouse，猫位置为 cat，回合数为 turns 时的游戏结果\n",
    "#         dp = [[[-1] * (2 * n * (n - 1)) for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "#         def getResult(mouse: int, cat: int, turns: int) -> int:\n",
    "#             # 如果已经达到最大回合数，返回平局\n",
    "#             if turns == 2 * n * (n - 1):\n",
    "#                 return DRAW\n",
    "            \n",
    "#             res = dp[mouse][cat][turns]\n",
    "#             if res != -1:\n",
    "#                 return res\n",
    "            \n",
    "#             # 判断老鼠是否已经到达洞口\n",
    "#             if mouse == 0:\n",
    "#                 res = MOUSE_WIN\n",
    "#             # 判断猫是否和老鼠在同一位置\n",
    "#             elif cat == mouse:\n",
    "#                 res = CAT_WIN\n",
    "#             else:\n",
    "#                 res = getNextResult(mouse, cat, turns)\n",
    "                \n",
    "#             dp[mouse][cat][turns] = res\n",
    "#             return res\n",
    "\n",
    "#         def getNextResult(mouse: int, cat: int, turns: int) -> int:\n",
    "#             curMove = mouse if turns % 2 == 0 else cat\n",
    "#             defaultRes = MOUSE_WIN if curMove != mouse else CAT_WIN\n",
    "#             res = defaultRes\n",
    "            \n",
    "#             for next in graph[curMove]:\n",
    "#                 if curMove == cat and next == 0: #跳过猫的0节点\n",
    "#                     continue\n",
    "#                 nextMouse = next if curMove == mouse else mouse\n",
    "#                 nextCat = next if curMove == cat else cat\n",
    "#                 nextRes = getResult(nextMouse, nextCat, turns + 1)\n",
    "                \n",
    "#                 if nextRes != defaultRes:\n",
    "#                     res = nextRes\n",
    "#                     if res != DRAW:\n",
    "#                         break\n",
    "                        \n",
    "#             return res\n",
    "\n",
    "#         # 从初始状态（老鼠在位置 1，猫在位置 2，回合数为 0）开始游戏\n",
    "#         return getResult(1, 2, 0)\n",
    "# 定义常量，用于标识不同的状态和角色\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        \n",
    "        # degrees数组记录每个状态下鼠和猫的度数\n",
    "        # results数组记录每个状态下的结果\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # 初始化degrees数组\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        \n",
    "        # 特殊处理：对于初始状态，鼠在洞中，结果为MOUSE_WIN\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        # 使用队列来进行状态转移的广度优先搜索\n",
    "        q = deque()\n",
    "        \n",
    "        # 初始化队列，将初始状态加入队列，并标记为MOUSE_WIN\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        \n",
    "        # 处理猫在洞中的情况，结果为CAT_WIN\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        # 开始广度优先搜索\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            \n",
    "            # 根据当前轮次确定前一轮次的状态\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            \n",
    "            # 遍历前一轮次的状态\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                # 特殊处理：如果猫抓住了鼠，继续下一轮\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                \n",
    "                # 如果前一轮的状态还没有确定结果（DRAW），则根据当前轮次的结果来确定前一轮次的结果\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    # 判断当前轮次的结果是否为MOUSE_WIN，并且前一轮次的轮次与当前轮次相同\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        # 如果前一轮次不能赢，减少其度数\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        # 如果度数减为0，确定前一轮次的结果\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        \n",
    "        # 返回结果\n",
    "        return results[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Deque\n",
    "from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    从确定的结果往回倒推，由于图是双向的，每遍历一个确定的结果就能知道这个确定的结果可能\n",
    "    是由哪些上一轮结果变过来的，如果上一轮猫或者老鼠的走法能保证当前自己获胜，那么按照题意，\n",
    "    上一轮的操作对象一定会走这个获胜的走法，进而就能得到上一轮也是必胜的结果。其他平局和必败\n",
    "    的情况，都需要尝试走完能到达当前结果的所有上一轮操作，所有的可能映射成节点的度，由于只有\n",
    "    确定的结果才会遍历上一轮可能得操作，每遍历一个确定结果的操作路径都将上一轮操作的度减一，\n",
    "    当上一轮操作减到0，说明所有的操作都确定无法保证上一轮操作的对象必胜，只能是必败了（如果是\n",
    "    平局，不会被遍历到，所以入度也不会减少）\n",
    "    '''\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        '''\n",
    "        存在三个维度：当前老鼠所在节点，当前猫所在节点，当前哪方操作\n",
    "        degree[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的度\n",
    "        result[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的结果，默认为0平局\n",
    "        '''\n",
    "        mouse_win, cat_win, draw, mouse_turn, cat_turn = 1, 2, 0, 0, 1\n",
    "        n = len(graph)\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        ''' \n",
    "        初始化各种组合下的度，由于猫不能走到0节点，因此不存在degree[i][0][cat_turn]这种组合的度\n",
    "        ''' \n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][mouse_turn] = len(graph[i])\n",
    "                degree[i][j][cat_turn] = len(graph[j])\n",
    "        ''' \n",
    "        上面是排除了当前猫已经在0节点的情况，但是没有排除从非0节点轮到猫走时，下一步走到0节点的情况，\n",
    "        这里就是将这种情况的度进行排除\n",
    "        ''' \n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][cat_turn] -= 1\n",
    "        ''' \n",
    "        初始化最终能确定结果的情况，并将这些情况放入队列中作为拓扑排序的起点\n",
    "        ''' \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            result[i][i][cat_turn] = cat_win\n",
    "            result[i][i][mouse_turn] = cat_win\n",
    "            q.append((i, i, cat_turn))\n",
    "            q.append((i, i, mouse_turn))\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            result[0][i][cat_turn] = mouse_win\n",
    "            result[0][i][mouse_turn] = mouse_win\n",
    "            q.append((0, i, cat_turn))\n",
    "            q.append((0, i, mouse_turn))\n",
    "        \n",
    "        while q:\n",
    "            cmn, ccn, ct = q.popleft()\n",
    "            cur = result[cmn][ccn][ct]\n",
    "            '''\n",
    "            根据当前的是哪方走推出上一轮是哪方走，将满足条件的可能都列出来\n",
    "            '''\n",
    "            if ct == mouse_turn:\n",
    "                prev = [(cmn, i, cat_turn) for i in graph[ccn]]\n",
    "            else:\n",
    "                prev = [(i, ccn, mouse_turn) for i in graph[cmn]]\n",
    "            \n",
    "            for pmn, pcn, pt in prev:\n",
    "                '''\n",
    "                猫不能走到0节点\n",
    "                '''\n",
    "                if not pcn:\n",
    "                    continue\n",
    "                '''\n",
    "                已经有确定结果了就不处理了，相当于visited\n",
    "                '''\n",
    "                if result[pmn][pcn][pt] != draw:\n",
    "                    continue\n",
    "                ''' \n",
    "                判断是不是必胜的情况\n",
    "                ''' \n",
    "                win = cur == mouse_win and pt == mouse_turn or cur == cat_win and pt == cat_turn\n",
    "                if win:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "                    continue\n",
    "                ''' \n",
    "                每排除一种可能将上一轮的度减一，如果到0了，就说明上一轮的结果是确定的，由于上面判断了必胜，平局的度\n",
    "                不可能为0，那么这里实际上是必败的情况\n",
    "                ''' \n",
    "                degree[pmn][pcn][pt] -= 1\n",
    "                if not degree[pmn][pcn][pt]:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "        \n",
    "        return result[1][2][mouse_turn]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        # degrees 表示每个状态的度数，results 表示每个状态的结果\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)] #是一个n x n x 2的三维矩阵\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # 计算每个状态的度数，即出边的数量\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        \n",
    "        # 考虑从位置 0 出发的情况，减少与猫的度数\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        # 初始化队列并将初始状态加入队列\n",
    "        q = deque()\n",
    "        #这里初始化了一些状态，具体来说，对于从位置0出发到达位置j的情况，老鼠和猫都是获胜的。将这些初始状态加入队列q中。\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        #这里初始化了一些状态，具体来说，对于老鼠和猫在同一个位置i的情况，猫总是获胜的。将这些初始状态加入队列q中。\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "      #这里开始处理队列中的状态，每次从队列中取出一个状态，其中mouse表示老鼠的位置，cat表示猫的位置，turn表示当前是老鼠还是猫的轮次，result表示当前状态的结果。\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            #根据当前轮次确定前一轮次的状态。如果当前轮次是老鼠轮次，那么前一轮次是猫轮次，反之亦然。prevStates是一个列表，其中包含了所有可能的前一状态。\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            \n",
    "            # 对于前一状态中，如果猫已经到达了位置0，那么不需要再考虑这种情况，因为游戏已经结束了。\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                  #对于前一状态中，如果前一状态的结果是平局，那么需要判断当前玩家是否可以获胜。如果当前玩家可以获胜，就更新前一状态的结果，并将前一状态加入队列。如果当前玩家不能获胜，就减少前一状态\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    # 判断当前玩家是否可以获胜\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        # 减少前一状态的度数\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            # 如果度数为 0，则另一玩家获胜\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Deque\n",
    "from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    从确定的结果往回倒推，由于图是双向的，每遍历一个确定的结果就能知道这个确定的结果可能\n",
    "    是由哪些上一轮结果变过来的，如果上一轮猫或者老鼠的走法能保证当前自己获胜，那么按照题意，\n",
    "    上一轮的操作对象一定会走这个获胜的走法，进而就能得到上一轮也是必胜的结果。其他平局和必败\n",
    "    的情况，都需要尝试走完能到达当前结果的所有上一轮操作，所有的可能映射成节点的度，由于只有\n",
    "    确定的结果才会遍历上一轮可能得操作，每遍历一个确定结果的操作路径都将上一轮操作的度减一，\n",
    "    当上一轮操作减到0，说明所有的操作都确定无法保证上一轮操作的对象必胜，只能是必败了（如果是\n",
    "    平局，不会被遍历到，所以入度也不会减少）\n",
    "    '''\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        '''\n",
    "        存在三个维度：当前老鼠所在节点，当前猫所在节点，当前哪方操作\n",
    "        degree[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的度\n",
    "        result[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的结果，默认为0平局\n",
    "        '''\n",
    "        mouse_win, cat_win, draw, mouse_turn, cat_turn = 1, 2, 0, 0, 1\n",
    "        n = len(graph)\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        ''' \n",
    "        初始化各种组合下的度，由于猫不能走到0节点，因此不存在degree[i][0][cat_turn]这种组合的度\n",
    "        ''' \n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][mouse_turn] = len(graph[i])\n",
    "                degree[i][j][cat_turn] = len(graph[j])\n",
    "        ''' \n",
    "        上面是排除了当前猫已经在0节点的情况，但是没有排除从非0节点轮到猫走时，下一步走到0节点的情况，\n",
    "        这里就是将这种情况的度进行排除\n",
    "        ''' \n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][cat_turn] -= 1\n",
    "        ''' \n",
    "        初始化最终能确定结果的情况，并将这些情况放入队列中作为拓扑排序的起点\n",
    "        ''' \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            result[i][i][cat_turn] = cat_win\n",
    "            result[i][i][mouse_turn] = cat_win\n",
    "            q.append((i, i, cat_turn))\n",
    "            q.append((i, i, mouse_turn))\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            result[0][i][cat_turn] = mouse_win\n",
    "            result[0][i][mouse_turn] = mouse_win\n",
    "            q.append((0, i, cat_turn))\n",
    "            q.append((0, i, mouse_turn))\n",
    "        \n",
    "        while q:\n",
    "            cmn, ccn, ct = q.popleft()\n",
    "            cur = result[cmn][ccn][ct]\n",
    "            '''\n",
    "            根据当前的是哪方走推出上一轮是哪方走，将满足条件的可能都列出来\n",
    "            '''\n",
    "            if ct == mouse_turn:\n",
    "                prev = [(cmn, i, cat_turn) for i in graph[ccn]]\n",
    "            else:\n",
    "                prev = [(i, ccn, mouse_turn) for i in graph[cmn]]\n",
    "            \n",
    "            for pmn, pcn, pt in prev:\n",
    "                '''\n",
    "                猫不能走到0节点\n",
    "                '''\n",
    "                if not pcn:\n",
    "                    continue\n",
    "                '''\n",
    "                已经有确定结果了就不处理了，相当于visited\n",
    "                '''\n",
    "                if result[pmn][pcn][pt] != draw:\n",
    "                    continue\n",
    "                ''' \n",
    "                判断是不是必胜的情况\n",
    "                ''' \n",
    "                win = cur == mouse_win and pt == mouse_turn or cur == cat_win and pt == cat_turn\n",
    "                if win:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "                    continue\n",
    "                ''' \n",
    "                每排除一种可能将上一轮的度减一，如果到0了，就说明上一轮的结果是确定的，由于上面判断了必胜，平局的度\n",
    "                不可能为0，那么这里实际上是必败的情况\n",
    "                ''' \n",
    "                degree[pmn][pcn][pt] -= 1\n",
    "                if not degree[pmn][pcn][pt]:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "        \n",
    "        return result[1][2][mouse_turn]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        mouse_win, cat_win, draw, mouse_turn, cat_turn = 1, 2, 0, 0, 1\n",
    "        n = len(graph)\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "    \n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][mouse_turn] = len(graph[i])\n",
    "                degree[i][j][cat_turn] = len(graph[j])\n",
    "        \n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][cat_turn] -= 1\n",
    "        \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            result[i][i][cat_turn] = cat_win\n",
    "            result[i][i][mouse_turn] = cat_win\n",
    "            q.append((i, i, cat_turn))\n",
    "            q.append((i, i, mouse_turn))\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            result[0][i][cat_turn] = mouse_win\n",
    "            result[0][i][mouse_turn] = mouse_win\n",
    "            q.append((0, i, cat_turn))\n",
    "            q.append((0, i, mouse_turn))\n",
    "        \n",
    "        while q:\n",
    "            cmn, ccn, ct = q.popleft()\n",
    "            cur = result[cmn][ccn][ct]\n",
    "            if ct == mouse_turn:\n",
    "                prev = [(cmn, i, cat_turn) for i in graph[ccn]]\n",
    "            else:\n",
    "                prev = [(i, ccn, mouse_turn) for i in graph[cmn]]\n",
    "            \n",
    "            for pmn, pcn, pt in prev:\n",
    "                if not pcn:\n",
    "                    continue\n",
    "                if result[pmn][pcn][pt] != draw:\n",
    "                    continue\n",
    "                \n",
    "                win = cur == mouse_win and pt == mouse_turn or cur == cat_win and pt == cat_turn\n",
    "                if win:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "                    continue\n",
    "                \n",
    "                degree[pmn][pcn][pt] -= 1\n",
    "                if not degree[pmn][pcn][pt]:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "        \n",
    "        return result[1][2][mouse_turn]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    从确定的结果往回倒推，由于图是双向的，每遍历一个确定的结果就能知道这个确定的结果可能\n",
    "    是由哪些上一轮结果变过来的，如果上一轮猫或者老鼠的走法能保证当前自己获胜，那么按照题意，\n",
    "    上一轮的操作对象一定会走这个获胜的走法，进而就能得到上一轮也是必胜的结果。其他平局和必败\n",
    "    的情况，都需要尝试走完能到达当前结果的所有上一轮操作，所有的可能映射成节点的度，由于只有\n",
    "    确定的结果才会遍历上一轮可能得操作，每遍历一个确定结果的操作路径都将上一轮操作的度减一，\n",
    "    当上一轮操作减到0，说明所有的操作都确定无法保证上一轮操作的对象必胜，只能是必败了（如果是\n",
    "    平局，不会被遍历到，所以入度也不会减少）\n",
    "    '''\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        '''\n",
    "        存在三个维度：当前老鼠所在节点，当前猫所在节点，当前哪方操作\n",
    "        degree[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的度\n",
    "        result[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的结果，默认为0平局\n",
    "        '''\n",
    "        mouse_win, cat_win, draw, mouse_turn, cat_turn = 1, 2, 0, 0, 1\n",
    "        n = len(graph)\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        ''' \n",
    "        初始化各种组合下的度，由于猫不能走到0节点，因此不存在degree[i][0][cat_turn]这种组合的度\n",
    "        ''' \n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][mouse_turn] = len(graph[i])\n",
    "                degree[i][j][cat_turn] = len(graph[j])\n",
    "        ''' \n",
    "        上面是排除了当前猫已经在0节点的情况，但是没有排除从非0节点轮到猫走时，下一步走到0节点的情况，\n",
    "        这里就是将这种情况的度进行排除\n",
    "        ''' \n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][cat_turn] -= 1\n",
    "        ''' \n",
    "        初始化最终能确定结果的情况，并将这些情况放入队列中作为拓扑排序的起点\n",
    "        ''' \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            result[i][i][cat_turn] = cat_win\n",
    "            result[i][i][mouse_turn] = cat_win\n",
    "            q.append((i, i, cat_turn))\n",
    "            q.append((i, i, mouse_turn))\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            result[0][i][cat_turn] = mouse_win\n",
    "            result[0][i][mouse_turn] = mouse_win\n",
    "            q.append((0, i, cat_turn))\n",
    "            q.append((0, i, mouse_turn))\n",
    "        \n",
    "        while q:\n",
    "            cmn, ccn, ct = q.popleft()\n",
    "            cur = result[cmn][ccn][ct]\n",
    "            '''\n",
    "            根据当前的是哪方走推出上一轮是哪方走，将满足条件的可能都列出来\n",
    "            '''\n",
    "            if ct == mouse_turn:\n",
    "                prev = [(cmn, i, cat_turn) for i in graph[ccn]]\n",
    "            else:\n",
    "                prev = [(i, ccn, mouse_turn) for i in graph[cmn]]\n",
    "            \n",
    "            for pmn, pcn, pt in prev:\n",
    "                '''\n",
    "                猫不能走到0节点\n",
    "                '''\n",
    "                if not pcn:\n",
    "                    continue\n",
    "                '''\n",
    "                已经有确定结果了就不处理了，相当于visited\n",
    "                '''\n",
    "                if result[pmn][pcn][pt] != draw:\n",
    "                    continue\n",
    "                ''' \n",
    "                判断是不是必胜的情况\n",
    "                ''' \n",
    "                win = cur == mouse_win and pt == mouse_turn or cur == cat_win and pt == cat_turn\n",
    "                if win:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "                    continue\n",
    "                ''' \n",
    "                每排除一种可能将上一轮的度减一，如果到0了，就说明上一轮的结果是确定的，由于上面判断了必胜，平局的度\n",
    "                不可能为0，那么这里实际上是必败的情况\n",
    "                ''' \n",
    "                degree[pmn][pcn][pt] -= 1\n",
    "                if not degree[pmn][pcn][pt]:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "        \n",
    "        return result[1][2][mouse_turn]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        CAT_TURN = 0\n",
    "        MOUSE_TURN = 1\n",
    "        CAT_WIN = 2\n",
    "        MOUSE_WIN = 1\n",
    "        DRAW = 0\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degree[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        res = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        q = deque([])\n",
    "        for j in range(1, n):\n",
    "            res[0][j][MOUSE_TURN] =  MOUSE_WIN\n",
    "            res[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            res[i][i][CAT_TURN] = CAT_WIN\n",
    "            res[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            q.append((i, i, CAT_TURN))\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "\n",
    "        while q:\n",
    "            mosue, cat, turn = q.popleft()\n",
    "            result = res[mosue][cat][turn]\n",
    "            if turn == CAT_TURN:\n",
    "                preState = [(prev, cat, MOUSE_TURN) for prev in graph[mosue]]\n",
    "            else:\n",
    "                preState = [(mosue, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            \n",
    "            for prevMouse, prevCat, PrevTurn in preState:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if res[prevMouse][prevCat][PrevTurn] == DRAW:\n",
    "                    canWin = (result == MOUSE_WIN and PrevTurn == MOUSE_TURN) or (result == CAT_WIN and PrevTurn == CAT_TURN)\n",
    "                    if canWin:\n",
    "                        res[prevMouse][prevCat][PrevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, PrevTurn))\n",
    "                    else:\n",
    "                        degree[prevMouse][prevCat][PrevTurn] -= 1\n",
    "                        if degree[prevMouse][prevCat][PrevTurn] == 0:\n",
    "                            res[prevMouse][prevCat][PrevTurn] = CAT_WIN if PrevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, PrevTurn))\n",
    "        return res[1][2][MOUSE_TURN]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Deque\n",
    "from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from typing import List, Deque\n",
    "# from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    从确定的结果往回倒推，由于图是双向的，每遍历一个确定的结果就能知道这个确定的结果可能\n",
    "    是由哪些上一轮结果变过来的，如果上一轮猫或者老鼠的走法能保证当前自己获胜，那么按照题意，\n",
    "    上一轮的操作对象一定会走这个获胜的走法，进而就能得到上一轮也是必胜的结果。其他平局和必败\n",
    "    的情况，都需要尝试走完能到达当前结果的所有上一轮操作，所有的可能映射成节点的度，由于只有\n",
    "    确定的结果才会遍历上一轮可能得操作，每遍历一个确定结果的操作路径都将上一轮操作的度减一，\n",
    "    当上一轮操作减到0，说明所有的操作都确定无法保证上一轮操作的对象必胜，只能是必败了（如果是\n",
    "    平局，不会被遍历到，所以入度也不会减少）\n",
    "    '''\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        '''\n",
    "        存在三个维度：当前老鼠所在节点，当前猫所在节点，当前哪方操作\n",
    "        degree[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的度\n",
    "        result[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的结果，默认为0平局\n",
    "        '''\n",
    "        mouse_win, cat_win, draw, mouse_turn, cat_turn = 1, 2, 0, 0, 1\n",
    "        n = len(graph)\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        ''' \n",
    "        初始化各种组合下的度，由于猫不能走到0节点，因此不存在degree[i][0][cat_turn]这种组合的度\n",
    "        ''' \n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][mouse_turn] = len(graph[i])\n",
    "                degree[i][j][cat_turn] = len(graph[j])\n",
    "        ''' \n",
    "        上面是排除了当前猫已经在0节点的情况，但是没有排除从非0节点轮到猫走时，下一步走到0节点的情况，\n",
    "        这里就是将这种情况的度进行排除\n",
    "        ''' \n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][cat_turn] -= 1\n",
    "        ''' \n",
    "        初始化最终能确定结果的情况，并将这些情况放入队列中作为拓扑排序的起点\n",
    "        ''' \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            result[i][i][cat_turn] = cat_win\n",
    "            result[i][i][mouse_turn] = cat_win\n",
    "            q.append((i, i, cat_turn))\n",
    "            q.append((i, i, mouse_turn))\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            result[0][i][cat_turn] = mouse_win\n",
    "            result[0][i][mouse_turn] = mouse_win\n",
    "            q.append((0, i, cat_turn))\n",
    "            q.append((0, i, mouse_turn))\n",
    "        \n",
    "        while q:\n",
    "            cmn, ccn, ct = q.popleft()\n",
    "            cur = result[cmn][ccn][ct]\n",
    "            '''\n",
    "            根据当前的是哪方走推出上一轮是哪方走，将满足条件的可能都列出来\n",
    "            '''\n",
    "            if ct == mouse_turn:\n",
    "                prev = [(cmn, i, cat_turn) for i in graph[ccn]]\n",
    "            else:\n",
    "                prev = [(i, ccn, mouse_turn) for i in graph[cmn]]\n",
    "            \n",
    "            for pmn, pcn, pt in prev:\n",
    "                '''\n",
    "                猫不能走到0节点\n",
    "                '''\n",
    "                if not pcn:\n",
    "                    continue\n",
    "                '''\n",
    "                已经有确定结果了就不处理了，相当于visited\n",
    "                '''\n",
    "                if result[pmn][pcn][pt] != draw:\n",
    "                    continue\n",
    "                ''' \n",
    "                判断是不是必胜的情况\n",
    "                ''' \n",
    "                win = cur == mouse_win and pt == mouse_turn or cur == cat_win and pt == cat_turn\n",
    "                if win:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "                    continue\n",
    "                ''' \n",
    "                每排除一种可能将上一轮的度减一，如果到0了，就说明上一轮的结果是确定的，由于上面判断了必胜，平局的度\n",
    "                不可能为0，那么这里实际上是必败的情况\n",
    "                ''' \n",
    "                degree[pmn][pcn][pt] -= 1\n",
    "                if not degree[pmn][pcn][pt]:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "        \n",
    "        return result[1][2][mouse_turn]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from typing import List, Deque\n",
    "# from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from typing import List, Deque\n",
    "# from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Deque\n",
    "from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "        for y in graph[0]:\n",
    "            for i in range(n):\n",
    "                degrees[i][y][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Deque\n",
    "from collections import deque\n",
    "\n",
    "class Solution :\n",
    "    \n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        # Define constants for clarity\n",
    "        MOUSE_TURN, CAT_TURN = 0, 1\n",
    "        DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2\n",
    "        \n",
    "        n = len(graph)\n",
    "        \n",
    "        # Initialize degree and result arrays\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[DRAW, DRAW] for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        # Set degree values based on graph structure\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degree[i][j][CAT_TURN] = len(graph[j])\n",
    "                \n",
    "        # Decrease degree for cat's invalid moves to node 0\n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][CAT_TURN] -= 1\n",
    "        \n",
    "        # Initialize outcomes where the results are already known\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[i][i][turn] = CAT_WIN\n",
    "                q.append((i, i, turn))\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            for turn in [MOUSE_TURN, CAT_TURN]:\n",
    "                result[0][i][turn] = MOUSE_WIN\n",
    "                q.append((0, i, turn))\n",
    "        \n",
    "        # Process states using BFS (based on topological sort)\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            \n",
    "            # Determine previous state based on current turn\n",
    "            if turn == MOUSE_TURN:\n",
    "                prev_states = [(mouse, next_cat, CAT_TURN) for next_cat in graph[cat]]\n",
    "            else:\n",
    "                prev_states = [(next_mouse, cat, MOUSE_TURN) for next_mouse in graph[mouse]]\n",
    "            \n",
    "            for pm, pc, pt in prev_states:\n",
    "                if not pc:  # Cat can't move to node 0\n",
    "                    continue\n",
    "                if result[pm][pc][pt] != DRAW:  # Skip already decided states\n",
    "                    continue\n",
    "                \n",
    "                # If current move leads to win for the current player\n",
    "                if (result[mouse][cat][turn] == MOUSE_WIN and pt == MOUSE_TURN) or \\\n",
    "                   (result[mouse][cat][turn] == CAT_WIN and pt == CAT_TURN):\n",
    "                    result[pm][pc][pt] = result[mouse][cat][turn]\n",
    "                    q.append((pm, pc, pt))\n",
    "                else:\n",
    "                    degree[pm][pc][pt] -= 1\n",
    "                    if degree[pm][pc][pt] == 0:  # All moves lead to loss for previous player\n",
    "                        result[pm][pc][pt] = MOUSE_WIN if pt == CAT_TURN else CAT_WIN\n",
    "                        q.append((pm, pc, pt))\n",
    "        \n",
    "        return result[1][2][MOUSE_TURN]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOUSE_TURN = 0\n",
    "CAT_TURN = 1\n",
    "\n",
    "DRAW = 0\n",
    "MOUSE_WIN = 1\n",
    "CAT_WIN = 2\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        n = len(graph)\n",
    "\n",
    "        degrees = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        results = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degrees[i][j][MOUSE_TURN] = len(graph[i])\n",
    "                degrees[i][j][CAT_TURN] = len(graph[j])\n",
    "\n",
    "        for j in graph[0]:\n",
    "            for i in range(n):\n",
    "                # 猫不走0，所以把连着 0  的度-1\n",
    "                degrees[i][j][CAT_TURN] -= 1\n",
    "\n",
    "        q = deque()\n",
    "\n",
    "        for j in range(1, n):\n",
    "            results[0][j][MOUSE_TURN] = MOUSE_WIN\n",
    "            results[0][j][CAT_TURN] = MOUSE_WIN\n",
    "            q.append((0, j, MOUSE_TURN))\n",
    "            q.append((0, j, CAT_TURN))\n",
    "        for i in range(1, n):\n",
    "            results[i][i][MOUSE_TURN] = CAT_WIN\n",
    "            results[i][i][CAT_TURN] = CAT_WIN\n",
    "            q.append((i, i, MOUSE_TURN))\n",
    "            q.append((i, i, CAT_TURN))\n",
    "\n",
    "        while q:\n",
    "            mouse, cat, turn = q.popleft()\n",
    "            result = results[mouse][cat][turn]\n",
    "            if turn == MOUSE_TURN:\n",
    "                prevStates = [(mouse, prev, CAT_TURN) for prev in graph[cat]]\n",
    "            else:\n",
    "                prevStates = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            for prevMouse, prevCat, prevTurn in prevStates:\n",
    "                if prevCat == 0:\n",
    "                    continue\n",
    "                if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "                    canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "                    if canWin:\n",
    "                        results[prevMouse][prevCat][prevTurn] = result\n",
    "                        q.append((prevMouse, prevCat, prevTurn))\n",
    "                    else:\n",
    "                        degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "                        if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "                            results[prevMouse][prevCat][prevTurn] = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "                            q.append((prevMouse, prevCat, prevTurn))\n",
    "        return results[1][2][MOUSE_TURN]\n",
    "\n",
    "\n",
    "\n",
    "        # while q:\n",
    "        #     mouse, cat, turn = q.popleft()\n",
    "        #     result = results[mouse][cat][turn]\n",
    "        #     if turn == MOUSE_TURN:\n",
    "        #         prevMov = [(mouse, prev, CAT_TURN) for prev in graph[cat]]#遍历前一步可能的猫的来源\n",
    "        #     else:\n",
    "        #         prevMov = [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]\n",
    "            \n",
    "        #     for prevMouse, prevCat, prevTurn in prevMov:\n",
    "        #         if prevCat == 0:\n",
    "        #             continue\n",
    "        #         if results[prevMouse][prevCat][prevTurn] == DRAW:\n",
    "        #             canWin = result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN\n",
    "        #             if canWin:\n",
    "        #                 results[prevMouse][prevCat][prevTurn] = result\n",
    "        #                 q.append((prevMouse, prevCat, prevTurn))\n",
    "        #             else:\n",
    "        #                 degrees[prevMouse][prevCat][prevTurn] -= 1\n",
    "        #                 if degrees[prevMouse][prevCat][prevTurn] == 0:\n",
    "        #                     results[prevMouse][prevCat][prevTurn] == CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN\n",
    "        #                     q.append((prevMouse, prevCat, prevTurn))\n",
    "\n",
    "        # return results[1][2][MOUSE_TURN]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    从确定的结果往回倒推，由于图是双向的，每遍历一个确定的结果就能知道这个确定的结果可能\n",
    "    是由哪些上一轮结果变过来的，如果上一轮猫或者老鼠的走法能保证当前自己获胜，那么按照题意，\n",
    "    上一轮的操作对象一定会走这个获胜的走法，进而就能得到上一轮也是必胜的结果。其他平局和必败\n",
    "    的情况，都需要尝试走完能到达当前结果的所有上一轮操作，所有的可能映射成节点的度，由于只有\n",
    "    确定的结果才会遍历上一轮可能得操作，每遍历一个确定结果的操作路径都将上一轮操作的度减一，\n",
    "    当上一轮操作减到0，说明所有的操作都确定无法保证上一轮操作的对象必胜，只能是必败了（如果是\n",
    "    平局，不会被遍历到，所以入度也不会减少）\n",
    "    '''\n",
    "    def catMouseGame(self, graph: List[List[int]]) -> int:\n",
    "        '''\n",
    "        存在三个维度：当前老鼠所在节点，当前猫所在节点，当前哪方操作\n",
    "        degree[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的度\n",
    "        result[i][j][0/1] 表示老鼠在节点i、猫在节点j，当前是老鼠/猫 这种组合下的结果，默认为0平局\n",
    "        '''\n",
    "        mouse_win, cat_win, draw, mouse_turn, cat_turn = 1, 2, 0, 0, 1\n",
    "        n = len(graph)\n",
    "        degree = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        result = [[[0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        ''' \n",
    "        初始化各种组合下的度，由于猫不能走到0节点，因此不存在degree[i][0][cat_turn]这种组合的度\n",
    "        ''' \n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                degree[i][j][mouse_turn] = len(graph[i])\n",
    "                degree[i][j][cat_turn] = len(graph[j])\n",
    "        ''' \n",
    "        上面是排除了当前猫已经在0节点的情况，但是没有排除从非0节点轮到猫走时，下一步走到0节点的情况，\n",
    "        这里就是将这种情况的度进行排除\n",
    "        ''' \n",
    "        for i in graph[0]:\n",
    "            for j in range(n):\n",
    "                degree[j][i][cat_turn] -= 1\n",
    "        ''' \n",
    "        初始化最终能确定结果的情况，并将这些情况放入队列中作为拓扑排序的起点\n",
    "        ''' \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            result[i][i][cat_turn] = cat_win\n",
    "            result[i][i][mouse_turn] = cat_win\n",
    "            q.append((i, i, cat_turn))\n",
    "            q.append((i, i, mouse_turn))\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            result[0][i][cat_turn] = mouse_win\n",
    "            result[0][i][mouse_turn] = mouse_win\n",
    "            q.append((0, i, cat_turn))\n",
    "            q.append((0, i, mouse_turn))\n",
    "        \n",
    "        while q:\n",
    "            cmn, ccn, ct = q.popleft()\n",
    "            cur = result[cmn][ccn][ct]\n",
    "            '''\n",
    "            根据当前的是哪方走推出上一轮是哪方走，将满足条件的可能都列出来\n",
    "            '''\n",
    "            if ct == mouse_turn:\n",
    "                prev = [(cmn, i, cat_turn) for i in graph[ccn]]\n",
    "            else:\n",
    "                prev = [(i, ccn, mouse_turn) for i in graph[cmn]]\n",
    "            \n",
    "            for pmn, pcn, pt in prev:\n",
    "                '''\n",
    "                猫不能走到0节点\n",
    "                '''\n",
    "                if not pcn:\n",
    "                    continue\n",
    "                '''\n",
    "                已经有确定结果了就不处理了，相当于visited\n",
    "                '''\n",
    "                if result[pmn][pcn][pt] != draw:\n",
    "                    continue\n",
    "                ''' \n",
    "                判断是不是必胜的情况\n",
    "                ''' \n",
    "                win = cur == mouse_win and pt == mouse_turn or cur == cat_win and pt == cat_turn\n",
    "                if win:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "                    continue\n",
    "                ''' \n",
    "                每排除一种可能将上一轮的度减一，如果到0了，就说明上一轮的结果是确定的，由于上面判断了必胜，平局的度\n",
    "                不可能为0，那么这里实际上是必败的情况\n",
    "                ''' \n",
    "                degree[pmn][pcn][pt] -= 1\n",
    "                if not degree[pmn][pcn][pt]:\n",
    "                    result[pmn][pcn][pt] = cur\n",
    "                    q.append((pmn, pcn, pt))\n",
    "        \n",
    "        return result[1][2][mouse_turn]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import namedtuple, defaultdict\n",
    "from itertools import product\n",
    "from typing import List\n",
    "\n",
    "Status = namedtuple('Status', ('ini','ip','op')) # 先手者, 先手者位置, 后手者位置\n",
    "DRAW, WIN, LOSE = 0, 1, 2 \n",
    "CAT, MOUSE = 0, 1\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, adj: List[List[int]]) -> int:\n",
    "        out = {}  \n",
    "        cac = defaultdict(lambda: DRAW)\n",
    "        queue = []\n",
    "\n",
    "        def set_result(status, result):\n",
    "            cac[status] = result\n",
    "            queue.append((status, result))\n",
    "\n",
    "        for ini,p in product((CAT, MOUSE), range(1, len(adj))): \n",
    "            set_result(Status(ini, p, p), WIN if ini==CAT else LOSE)\n",
    "            set_result(Status(ini, p, 0), LOSE if ini==CAT else WIN)\n",
    "\n",
    "        while queue:\n",
    "            sta, result = queue.pop()\n",
    "            for prvip in adj[sta.op]:\n",
    "                prvSta = Status(1 ^ sta.ini, prvip, sta.ip)\n",
    "                if prvSta in cac:\n",
    "                    continue\n",
    "                if result == LOSE:\n",
    "                    set_result(prvSta, WIN)\n",
    "                else: \n",
    "                    out[prvSta] = out.get(prvSta, len(adj[prvip])) - 1\n",
    "                    if out[prvSta] == 0:\n",
    "                        set_result(prvSta, LOSE)\n",
    "\n",
    "        return cac[Status(MOUSE, 1, 2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DRAW, WIN, LOSE = 0, 1, 2\n",
    "CAT, MOUSE = 0, 1\n",
    "class Solution:\n",
    "    def catMouseGame(self, adj: List[List[int]]) -> int:\n",
    "        out, cac, queue = {}, defaultdict(lambda: DRAW), []\n",
    "\n",
    "        def set_result(status, result):\n",
    "            cac[status] = result\n",
    "            queue.append((status, result))\n",
    "        \n",
    "        for ini, p in product((CAT, MOUSE), range(1, len(adj))): \n",
    "            set_result((ini, p, p), WIN if ini==CAT else LOSE)\n",
    "            set_result((ini, p, 0), LOSE if ini==CAT else WIN)\n",
    "        for sta, result in queue:\n",
    "            for prvip in adj[sta[2]]:\n",
    "                prvSta = (1 ^ sta[0], prvip, sta[1])\n",
    "                if prvSta in cac: continue\n",
    "                if result == LOSE:\n",
    "                    set_result(prvSta, WIN)\n",
    "                else: \n",
    "                    out[prvSta] = out.get(prvSta, len(adj[prvip])) - 1\n",
    "                    if out[prvSta] == 0:\n",
    "                        set_result(prvSta, LOSE)\n",
    "        return cac[(MOUSE, 1, 2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, adj: List[List[int]]) -> int:\n",
    "        d = defaultdict(int) # 存三元组（先手，先手者位置，后手者位置）的输赢结果\n",
    "        in_deg, q = {}, []   # 对三元组状态建图，然后在图上拓扑排序\n",
    "        DRAW, WIN, LOSE = 0, 1, 2\n",
    "        CAT, MOUSE = 0, 1\n",
    "        # 设置状态的输赢结果并存进队列\n",
    "        def set_res(status, res):\n",
    "            d[status] = res \n",
    "            q.append((status, res))\n",
    "        \n",
    "        # 找初始边界状态\n",
    "        for ini, pos in product((CAT, MOUSE), range(1, len(adj))):\n",
    "            set_res((ini, pos, pos), LOSE if ini == MOUSE else WIN)\n",
    "            set_res((ini, pos, 0), WIN if ini == MOUSE else LOSE)\n",
    "\n",
    "        for cur_status, cur_res in q:\n",
    "            # 自底向上转移，有向图的方向是从这一手操作到上一手操作\n",
    "            for pre_ip in adj[cur_status[2]]:\n",
    "                # 上一手的先手是当前后手\n",
    "                # 上一手的先手位置是这一手的后手位置的邻居\n",
    "                # 上一手的后手位置是这一手的先手位置\n",
    "                pre_status = (1 ^ cur_status[0], pre_ip, cur_status[1])\n",
    "                if pre_status in d:\n",
    "                    continue\n",
    "                if cur_res == LOSE:\n",
    "                    set_res(pre_status, WIN) #这一手必负，则上一手必胜\n",
    "                else:\n",
    "                    in_deg[pre_status] = in_deg.get(pre_status, len(adj[pre_ip])) - 1\n",
    "                    #上一手只能到达这一手的先手必胜态，则上一手必负\n",
    "                    if in_deg[pre_status] == 0:\n",
    "                        set_res(pre_status, LOSE)\n",
    "        return d[(MOUSE, 1, 2)]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DRAW, WIN, LOSE = 0, 1, 2\n",
    "CAT, MOUSE = 0, 1\n",
    "class Solution:\n",
    "    def catMouseGame(self, adj: List[List[int]]) -> int:\n",
    "        d = defaultdict(int) # 存三元组（先手，先手者位置，后手者位置）的输赢结果\n",
    "        q = []\n",
    "        in_deg = {}\n",
    "\n",
    "        # 设置状态的输赢结果并存进队列\n",
    "        def set_res(status, res):\n",
    "            d[status] = res \n",
    "            q.append((status, res))\n",
    "        \n",
    "        # 找边界状态\n",
    "        for ini, pos in product((CAT, MOUSE), range(1, len(adj))):\n",
    "            set_res((ini, pos, pos), LOSE if ini == MOUSE else WIN)\n",
    "            set_res((ini, pos, 0), WIN if ini == MOUSE else LOSE)\n",
    "\n",
    "        for cur_status, cur_res in q:\n",
    "            # 自底向上转移，有向图的方向是从这一手操作到上一手操作\n",
    "            for pre_ip in adj[cur_status[2]]:\n",
    "                # 上一手的先手是当前后手\n",
    "                # 上一手的先手位置是这一手的后手位置的邻居\n",
    "                # 上一手的后手位置是这一手的先手位置\n",
    "                pre_status = (1 ^ cur_status[0], pre_ip, cur_status[1])\n",
    "                if pre_status in d:\n",
    "                    continue\n",
    "                if cur_res == LOSE:\n",
    "                    set_res(pre_status, WIN) #这一手必负，则上一手必胜\n",
    "                else:\n",
    "                    in_deg[pre_status] = in_deg.get(pre_status, len(adj[pre_ip])) - 1\n",
    "                    #上一手只能到达这一手的先手必胜态，则上一手必负\n",
    "                    if in_deg[pre_status] == 0:\n",
    "                        set_res(pre_status, LOSE)\n",
    "        return d[(MOUSE, 1, 2)]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import namedtuple, defaultdict\n",
    "from itertools import product\n",
    "from typing import List\n",
    "\n",
    "Status = namedtuple('Status', ('ini','ip','op')) # 先手者, 先手者位置, 后手者位置\n",
    "DRAW, WIN, LOSE = 0, 1, 2 \n",
    "CAT, MOUSE = 0, 1\n",
    "\n",
    "class Solution:\n",
    "    def catMouseGame(self, adj: List[List[int]]) -> int:\n",
    "        out = {}  \n",
    "        cac = defaultdict(lambda: DRAW)\n",
    "        queue = []\n",
    "\n",
    "        def set_result(status, result):\n",
    "            cac[status] = result\n",
    "            queue.append((status, result))\n",
    "\n",
    "        for ini,p in product((CAT, MOUSE), range(1, len(adj))): \n",
    "            set_result(Status(ini, p, p), WIN if ini==CAT else LOSE)\n",
    "            set_result(Status(ini, p, 0), LOSE if ini==CAT else WIN)\n",
    "\n",
    "        while queue:\n",
    "            sta, result = queue.pop()\n",
    "            for prvip in adj[sta.op]:\n",
    "                prvSta = Status(1 ^ sta.ini, prvip, sta.ip)\n",
    "                if prvSta in cac:\n",
    "                    continue\n",
    "                if result == LOSE:\n",
    "                    set_result(prvSta, WIN)\n",
    "                else: \n",
    "                    out[prvSta] = out.get(prvSta, len(adj[prvip])) - 1\n",
    "                    if out[prvSta] == 0:\n",
    "                        set_result(prvSta, LOSE)\n",
    "\n",
    "        return cac[Status(MOUSE, 1, 2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def catMouseGame(self, graph):\n",
    "        N = len(graph)\n",
    "\n",
    "        # What nodes could play their turn to\n",
    "        # arrive at node (m, c, t) ?\n",
    "        def parents(m, c, t):\n",
    "            if t == 2:\n",
    "                for m2 in graph[m]:\n",
    "                    yield m2, c, 3-t\n",
    "            else:\n",
    "                for c2 in graph[c]:\n",
    "                    if c2:\n",
    "                        yield m, c2, 3-t\n",
    "\n",
    "        DRAW, MOUSE, CAT = 0, 1, 2\n",
    "        color = collections.defaultdict(int)\n",
    "\n",
    "        # degree[node] : the number of neutral children of this node\n",
    "        degree = {}\n",
    "        for m in range(N):\n",
    "            for c in range(N):\n",
    "                degree[m,c,1] = len(graph[m])\n",
    "                degree[m,c,2] = len(graph[c]) - (0 in graph[c])\n",
    "\n",
    "        # enqueued : all nodes that are colored\n",
    "        queue = collections.deque([])\n",
    "        for i in range(N):\n",
    "            for t in range(1, 3):\n",
    "                color[0, i, t] = MOUSE\n",
    "                queue.append((0, i, t, MOUSE))\n",
    "                if i > 0:\n",
    "                    color[i, i, t] = CAT\n",
    "                    queue.append((i, i, t, CAT))\n",
    "\n",
    "        # percolate\n",
    "        while queue:\n",
    "            # for nodes that are colored :\n",
    "            i, j, t, c = queue.popleft()\n",
    "            # for every parent of this node i, j, t :\n",
    "            for i2, j2, t2 in parents(i, j, t):\n",
    "                # if this parent is not colored :\n",
    "                if color[i2, j2, t2] is DRAW:\n",
    "                    # if the parent can make a winning move (ie. mouse to MOUSE), do so\n",
    "                    if t2 == c: # winning move\n",
    "                        color[i2, j2, t2] = c\n",
    "                        queue.append((i2, j2, t2, c))\n",
    "                    # else, this parent has degree[parent]--, and enqueue if all children\n",
    "                    # of this parent are colored as losing moves\n",
    "                    else:\n",
    "                        degree[i2, j2, t2] -= 1\n",
    "                        if degree[i2, j2, t2] == 0:\n",
    "                            color[i2, j2, t2] = 3 - t2\n",
    "                            queue.append((i2, j2, t2, 3 - t2))\n",
    "\n",
    "        return color[1, 2, 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "Status = namedtuple('Status', ('ini','ip','op')) # 先手者, 先手者位置, 后手者位置\n",
    "DRAW, WIN, LOSE = 0, 1, 2 # 状态值, 即该状态对于先手者是必胜态还是必负态\n",
    "CAT, MOUSE = 0, 1\n",
    "class Solution:\n",
    "    def catMouseGame(self, adj: List[List[int]]) -> int:\n",
    "        out = {}  # 状态 -> 连向的 平局或者必负态 的最大个数\n",
    "        # 这里没必要初始化`out`, 用到的时候再进行\n",
    "        cac = defaultdict(lambda: DRAW)\n",
    "        queue = []\n",
    "\n",
    "        def set_result(status, result):\n",
    "            cac[status] = result\n",
    "            queue.append((status, result))\n",
    "        # 最基本的两类状态\n",
    "        for ini,p in product((CAT, MOUSE), range(1, len(adj))): \n",
    "            set_result(Status(ini, p, p), WIN if ini==CAT else LOSE) # 老鼠进腹\n",
    "            set_result(Status(ini, p, 0), LOSE if ini==CAT else WIN) # 老鼠进洞\n",
    "\n",
    "        for sta, result in queue:\n",
    "            for prvip in adj[sta.op]:\n",
    "                prvSta = Status(1 ^ sta.ini, prvip, sta.ip)\n",
    "                # 保证状态不会重复放进`queue`\n",
    "                if prvSta in cac: continue\n",
    "                if result == LOSE: # 找出一个必负态, 就遍历所有必负态的相邻结点\n",
    "                    set_result(prvSta, WIN)\n",
    "                else: \n",
    "                    out[prvSta] = out.get(prvSta, len(adj[prvip])) - 1\n",
    "                    if out[prvSta] == 0:\n",
    "                        set_result(prvSta, LOSE)\n",
    "        return cac[Status(MOUSE, 1, 2)]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
